#include "assign.h"
#include <iostream>
#include <math.h>

int numOfApp;                   //app的数量
int numOfPM;                    //物理机的数量
float upBound, lowBound;        //理想状态下机器负载的阈值范围
float perBound;                 //每个app在每台机器上的CPU上限
float* vectorAppCPU = 0;        //每个App所需要的计算能力
int* vectorAppSize = 0;         //每个应用的大小，用于计算部署代价
bool* vectorAvailable = 0;

int** matrixAssign = 0;         //分配矩阵，表明App是否在PM上运行，以及是否存在实体
float** matrixState = 0;        //状态矩阵，用来表明每个App在每个PM上的负载
float** matrixCost = 0;         //部署代价矩阵
float* vectorMachineCPU = 0;    //每台物理机器的负载
int** matrixOut = 0;            //运算后的结果矩阵

/*
 * 按照当前分配矩阵计算当前的状态矩阵
 * 同时也会计算vectorMachineCPU
 */
void calculateMatrixState(){
    int i, j;
    int p;              //某个应用有多少个物理机器正在运行的累加器
    float stress;
    float minValue;
    int minID;
    for (i = 0; i < numOfApp; i++){
        p = 0;
        if (vectorAppCPU[i] < 0.0001){
            vectorAppCPU[i] = 0.0001;
        }
        for (j = 0; j < numOfPM; j++){
            if (vectorAvailable[j] && matrixOut[i][j] == STATE_RUNNING)
                p++;
        }
        if (p != 0){
            stress = (float)vectorAppCPU[i] / p;    //计算该应用在每个机器上的压力
            for (j = 0; j < numOfPM; j++){
                if (vectorAvailable[j] && matrixOut[i][j] == STATE_RUNNING){
                    matrixState[i][j] = stress;
                }else{
                    matrixState[i][j] = 0;
                }
            }
        }else{
            for (j = 0; j < numOfPM; j++){
                matrixState[i][j] = 0;
            }
        }
    }

    //根据上面计算好的状态矩阵，纵向求和，就算每台机器的负载
    for (j = 0; j < numOfPM; j++){
        stress = 0;
        for (i = 0; i < numOfApp; i++)
            stress += matrixState[i][j];
        vectorMachineCPU[j] = stress;
        if (stress > 1.0){
            stress = 1.0f;
        }
    }

    for (i = 0; i < numOfApp; i++){
        p = 0;
        for (j = 0; j < numOfPM; j++){
            if (vectorAvailable[j] && matrixOut[i][j] == STATE_RUNNING)
                p++;
        }
        if (p == 0){
            //当某个App没有在一台机器上有实例时，处理这种情况
            minValue = 9e9;
            for (int j = 0; j < numOfPM; j++){
                if (vectorAvailable[j]){
                    if (minValue > vectorMachineCPU[j]){
                        minValue = vectorMachineCPU[j];
                        minID = j;
                    }
                    if (matrixOut[i][j] == STATE_INSTANCE &&
                        vectorAppCPU[i] + vectorMachineCPU[j] < upBound){
                        minValue = 0;
                        minID = j;
                    }
                }
            }
            matrixState[i][minID] = vectorAppCPU[i];
            matrixOut[i][minID] = STATE_RUNNING;
            vectorMachineCPU[minID] += vectorAppCPU[i];
        }
    }
}

/*
 * 根据分配矩阵，计算出代价矩阵
 */
void calculateMatrixCost(){
    int i, j;
    for (i = 0; i < numOfApp; i++){
        for (j = 0; j < numOfPM; j++){
            if (matrixAssign[i][j] == STATE_RUNNING){
                //i应用在j机器上正在运行
                matrixCost[i][j] = 0;
            }else if(matrixAssign[i][j] == STATE_INSTANCE){
                //i应用在j机器上存在实例，但不在运行
                matrixCost[i][j] = COST_F5_COFF;
            }else{
                //i应用在j机器上不存在实例
                matrixCost[i][j] = vectorAppSize[i] * COST_SIZE_COFF + COST_F5_COFF;
            }
        }
    }
}

/*
 * 根据状态矩阵反推出app的需要
 */
void calculateAppNeeds(){
    int i, j;
    float sum;
    for (i = 0; i < numOfApp; i++){
        sum = 0;
        for (j = 0; j < numOfPM; j++){
            if (vectorAvailable[j]){
                sum += matrixState[i][j];
            }
        }
        vectorAppCPU[i] = sum;
    }
}

/*
 * 根据调整后的状态矩阵，利用代价矩阵和分配矩阵计算总代价
 */
float calculateCost(){
    int i, j;
    float result;
    result = 0;
    for (i = 0; i < numOfApp; i++){
        for (j = 0; j < numOfPM; j++){
            if (vectorAvailable[j]){
                if (matrixState[i][j] > 1e-6){
                    result += matrixCost[i][j];
                }
            }
        }
    }
    return result;
}

/*
 * 检测当前分配方式是否符合约束条件
 */
int checkConstraint(){
    calculateMatrixState();
    for (int j = 0; j < numOfPM; j++){
        if (vectorAvailable[j] &&
            (vectorMachineCPU[j] > upBound)) {
            return j;
        }
    }

    return -1;
}

/*
 * 分配矩阵内存
 */
void initMatrix(){
    int i;
    matrixAssign = new int*[numOfApp];
    for (i = 0; i < numOfApp; i++){
        matrixAssign[i] = new int[numOfPM];
    }

    matrixCost = new float*[numOfApp];
    for (i = 0; i < numOfApp; i++){
        matrixCost[i] = new float[numOfPM];
    }

    matrixState = new float*[numOfApp];
    for (i = 0; i < numOfApp; i++){
        matrixState[i] = new float[numOfPM];
    }

    matrixOut = new int*[numOfApp];
    for (i = 0; i < numOfApp; i++){
        matrixOut[i] = new int[numOfPM];
    }

    vectorAppCPU = new float[numOfApp];
    vectorAvailable = new bool[numOfPM];
    memset(vectorAvailable, 1, sizeof(bool) * numOfPM);
    vectorAppSize = new int[numOfApp];
    vectorMachineCPU = new float[numOfPM];
}

/*
 * 回收空间
 */
void destoryMatrix(){
    int i;
    if (matrixAssign != 0){
        for (i = 0; i < numOfApp; i++){
            delete[] matrixAssign[i];
        }
        delete[] matrixAssign;
    }

    if (matrixCost != 0){
        for (i = 0; i < numOfApp; i++){
            delete[] matrixCost[i];
        }
        delete[] matrixCost;
    }

    if (matrixState != 0){
        for (i = 0; i < numOfApp; i++){
            delete[] matrixState[i];
        }
        delete[] matrixState;
    }

    if (matrixOut != 0){
        for (i = 0; i < numOfApp; i++){
            delete[] matrixOut[i];
        }
        delete[] matrixOut;
    }
    if (vectorAppCPU != 0) delete[] vectorAppCPU;
    if (vectorAvailable != 0) delete[] vectorAvailable;
    if (vectorAppSize != 0) delete[] vectorAppSize;
    if (vectorMachineCPU != 0) delete[] vectorMachineCPU;
}

void copyArray(int** dest, int** src){
    for (int i = 0; i < numOfApp; i++){
        for (int j = 0; j < numOfPM; j++){
            dest[i][j] = src[i][j];
        }
    }
}

/*
 * 主计算函数
 */
void doCalculate(){
    /*
    int i, j;
    for (i = 0; i < numOfApp; i++){
        for (j = 0; j < numOfPM; j++){
            matrixAssign[i][j] = -1;
        }
    }

    for (j = 0; j < numOfApp; j++){
        matrixAssign[j][1] = 1;
        matrixAssign[j][0] = 1;
    }
    */
    
    int ret, citr;
    int machineNeeds, machineRunning;   //分别用于记录需要多少机器，以及实际有多少机器运行

    upBound = 0.7;
    lowBound = 0.3;
    perBound = 0.1;

    copyArray(matrixOut, matrixAssign);
    calculateMatrixState();
    printMachine();
    
    #ifdef DEBUG
    printAssign();
    #endif

    calculateCost();                        //计算代价矩阵

    machineNeeds = getMachineNeeds();       //根据当前总负载计算出需要多少机器
    machineRunning = getMachineRunning();   //根据分配矩阵得出实际有多少机器运行
    if (machineNeeds != machineRunning){
        if (machineNeeds > machineRunning){
            //如果机器数量不够，则按某些原则开启机器
            turnonMachine(machineNeeds - machineRunning);
        }else{
            //如果机器过多，则按某些原则关闭机器
            shutdownMachine(machineRunning - machineNeeds);
        } 
    }

    citr = 0;
    while ((ret = checkConstraint()) != -1 && citr < numOfApp){
        doAssign(ret);
        citr++;
    }

    printMachine();
    copyArray(matrixAssign, matrixOut);
    for (int j = 0; j < numOfPM; j++){
        if (!vectorAvailable[j]){
            for (int i = 0; i < numOfApp; i++){
                if (matrixAssign[i][j] == STATE_RUNNING){
                    matrixAssign[i][j] = STATE_INSTANCE;
                }
            }
        }
    }
}


void chooseMinAndAssign(float* sizes, float* values, int p){
    float* density = new float[numOfApp];
    float minValue = 9e9;
    int minID = 0;
    int* assigns = new int[numOfPM];
    for (int i = 0; i < numOfApp; i++){
        density[i] = values[i] / sizes[i];
        if (minValue > density[i]){
            minValue = density[i];
            minID = i;
        }
    }
    getMinValue(minID, p, sizes, values, assigns);
    for (int j = 0; j < numOfPM; j++){
        matrixOut[minID][j] = assigns[j];
    }
    delete[] density;
    delete[] assigns;
}

void getMinValue(int app, int machine, float* sizes,
                 float* values, int* assigns) {
    float size = 0;
    float value = 0;
    float minCPU = 9e9;
    int minID = 0;
    if (matrixOut[app][machine] != STATE_RUNNING){
        value = 9e9;
        size = 1;
    }else{
        for (int i = 0; i < numOfPM; i++){
            assigns[i] = matrixOut[app][i];
            if (vectorAvailable[i] && assigns[i] != STATE_RUNNING){
                /*
                if (minCPU > vectorMachineCPU[i]){
                    minCPU = vectorMachineCPU[i];
                    minID = i;
                }
                 */
                if (minCPU > matrixCost[app][i]
                    && vectorMachineCPU[i] + matrixState[app][machine] < upBound){
                    minCPU = matrixCost[app][i];
                    minID = i;
                }
            }
        }
        if (minCPU < 9e8){
            assigns[minID] = STATE_RUNNING;
            if (matrixState[app][machine] > perBound){
                assigns[machine] = STATE_RUNNING;
            }else{
                assigns[machine] = STATE_NOTHING;
            }
            size = matrixState[app][machine];
            value = matrixCost[app][minID];
        }else{
            value = 9e9;
            size = 1;
        }
    }

    sizes[app] = size;
    values[app] = value;
    return;
}

void doAssign(int p) {
    float* values = new float[numOfApp];
    float* sizes = new float[numOfApp];
    int* assigns = new int[numOfPM];

    for (int i = 0; i < numOfApp; i++){
        getMinValue(i, p, sizes , values, assigns);
    }
    chooseMinAndAssign(sizes, values, p);

    delete[] values;
    delete[] sizes;
    delete[] assigns;
}

/*
 * 按照当前的各个应用的负载情况，计算出需要多少台机器
 */
int getMachineNeeds(){
    int i;
    float stress;                       //总压力的累加器
    stress = 0;
    for (i = 0; i < numOfApp; i++){
        stress += vectorAppCPU[i];
    }
    return (int)ceil((stress / ((upBound + lowBound) * 0.5)));   //机器数=总负载/每台机器理想负载
}

/*
 * 根据当前的分配矩阵，计算出当前有多少台机器正在运行
 * 同时会根据分配矩阵，修改avaialbe数组
 */
int getMachineRunning(){
    int i, j, r;                                //r是正在运行的机器数量的累加器
    bool flag;                                  //是否有机器的标志位
    r = 0;
    for (j = 0; j < numOfPM; j++){
        if (vectorAvailable[j]){
            flag = false;
            for (i = 0; i < numOfApp; i++){
                if (matrixAssign[i][j] == STATE_RUNNING){
                    flag = true;                //有一个应用在运行，标志位置true
                    break;
                }
            }
            if (flag){
                r++;                            //此机器至少有一个应用正在运行
                vectorAvailable[j] = true;
            }else{
                vectorAvailable[j] = false;           //此机器没有一个应用在运行，将他关闭
            }
        }
    }
    return r;
}
/*
 * 根据当前的状态矩阵，选择最理想的n个机器关闭
 * 同时会根据负载情况，修改avaialbe数组
 */
void shutdownMachine(int n){
    int i, j, k;
    float cost, minCost;              //分别记录每个机器撤出后的代价，以及最小代价
    int minCostMachine;               //最小代价所用的机器
    for (k = 0 ; k < n; k++){         //依次关闭n台机器
        minCost = 99999;              //初始化最小代价为最大值
        minCostMachine = 0;
        for (j = 0; j < numOfPM; j++){
            if (vectorAvailable[j]){
                cost = 0;
                for (i = 0; i < numOfApp; i++){
                    if (matrixAssign[i][j] == STATE_RUNNING)
                        cost++;      //选择正在运行App数量最少的机器
                }
                if (cost < minCost){
                    minCost = cost;         //更新最小值
                    minCostMachine = j;
                }
            }
        }
        vectorAvailable[minCostMachine] = false;  //将此机器关闭
    }
}

/*
 * 根据当前的状态矩阵，选择最理想的n个机器打开
 * 同时会根据负载情况，修改avaialbe数组
 */
void turnonMachine(int n){
    int i, j, k;
    int cost, maxCost;                  //分别记录每个机器开启后的利益，以及最大利益
    int maxCostMachine;                 //最大利益所对应的机器
    for (k = 0; k < n; k++){            //依次打开n台机器
        maxCost = -99999;               //初始化最大利益
        maxCostMachine = 0;
        for (j = 0; j < numOfPM; j++){
            if (!vectorAvailable[j]){
                cost = 0;
                for (i = 0; i < numOfApp; i++){
                    if (matrixAssign[i][j] != STATE_NOTHING);
                        cost++;         //选择存在实例数最多的机器打开
                }
                if (cost > maxCost){
                    maxCost = cost;     //更新最大值
                    maxCostMachine = j;
                }
            }
        }
        vectorAvailable[maxCostMachine] = true;       //将此机器打开
    }
}

/*
 * 打印Assign矩阵
 */
void printAssign(){
    int i, j;
    printf("========== ASSIGN MATRIX ==========\n");

    printf("\t");
    for (j = 0; j < numOfPM; j++){
        if (vectorAvailable[j]){
            printf("PM%d\t", j);
        }else{
            printf("OFF\t");
        }
    }
    printf("\n");

    for (i = 0; i < numOfApp; i++){
        printf("App%d\t", i);
        for (j = 0; j < numOfPM; j++){
            printf("%d\t", matrixAssign[i][j]);
        }
        printf("\n");
    }
    printf("==========  END  MATRIX  ==========\n");
}

/*
 * 打印Cost矩阵
 */
void printCost(){
    int i, j;
    printf("==========  COST  MATRIX ==========\n");

    printf("\t");
    for (j = 0; j < numOfPM; j++){
        if (vectorAvailable[j]){
            printf("PM%d\t", j);
        }else{
            printf("OFF\t");
        }
    }
    printf("\n");

    for (i = 0; i < numOfApp; i++){
        printf("App%d\t", i);
        for (j = 0; j < numOfPM; j++){
            printf("%.2lf\t", matrixCost[i][j]);
        }
        printf("\n");
    }
    printf("==========  END  MATRIX  ==========\n");
}

/*
 * 打印State矩阵
 */
void printState(){
    int i, j;
    printf("========== STATE  MATRIX ==========\n");

    printf("\t");
    for (j = 0; j < numOfPM; j++){
        if (vectorAvailable[j]){
            printf("PM%d\t", j);
        }else{
            printf("OFF\t");
        }
    }
    printf("\n");

    for (i = 0; i < numOfApp; i++){
        printf("App%d\t", i);
        for (j = 0; j < numOfPM; j++){
            printf("%.2lf\t", matrixState[i][j]);
        }
        printf("\n");
    }

    printf("ALL:\t");
    for (j = 0; j < numOfPM; j++){
        printf("%.2lf\t", vectorMachineCPU[j]);
    }
    printf("\n");
    printf("==========  END  MATRIX  ==========\n");
}

/*
 * 打印机器状态
 */
void printMachine(){
    int j;
    printf("========== MACHINE STATE ==========\n");

    for (j = 0; j < numOfPM; j++){
        if (vectorAvailable[j]){
            printf("PM%d\t%f\n", j, vectorMachineCPU[j]);
        }else{
            printf("PM%d:\tOFF\n", j);
        }
    }
    printf("==========  END  PRINT  ==========\n");
}

